package q212_findWords;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution_2 {
    Set<String> set = new HashSet<>();
    List<String> ans = new ArrayList<>();
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int n, m;
    boolean[][] vis = new boolean[15][15];
    /*
    用纯DFS来解决此题
    为了避免一个单词在board中多次出现导致我们反复加入 每次加入ans一个单词 就从set中删掉该单词
    为了剪枝 按照题设可以当单词长度超过10的时候就return
     */
    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        for (String word : words) set.add(word);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vis[i][j] = true;
                sb.append(board[i][j]);
                dfs(board, sb, i, j);
                vis[i][j] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return ans;
    }

    public void dfs(char[][] board, StringBuilder sb, int i, int j) {
        if (sb.length() > 10) return;
        if (set.contains(sb.toString())) {
            ans.add(sb.toString());
            set.remove(sb.toString());
        }
        for (int[] d : dirs) {
            int dx = i + d[0], dy = j + d[1];
            if (dx < 0 || dx >= m || dy < 0 || dy >= n || vis[dx][dy]) continue;

            vis[dx][dy] = true;
            sb.append(board[dx][dy]);
            dfs(board, sb, dx, dy);
            vis[dx][dy] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
